Recently, as an error correcting code to realize high error correction performance in a feasible circuit scale, an LDPC (Low-Density Parity Check) code is popular. An LDPC code can provide high error correction performance and be implemented in a simple manner, and is therefore adopted in error correction coding schemes such as the fast wireless LAN system of IEEE802.11n and a digital broadcast system.
An LDPC code is an error correcting code defined by a low-density parity check matrix H. Here, a low density means that the number of elements of “1's” included in the matrix is greatly lower than the number of elements of “0's.” That is, an LDPC code is a block code having the same block length as the number of columns N of parity check matrix H.
However, like Ethernet (trademark), most of today's communication systems have a feature of performing communication based on variable-length packets or frames. If an LDPC code, which is a block code, is applied to such systems, for example, a problem arises as to how a fixed-length LDPC code block is applied to a variable-length Ethernet (trademark) frame. Here, an LDPC code is adopted in the wireless LAN standard of IEEE802.11n. In IEEE802.11n, padding or puncturing is applied to a transmission information sequence to adjust the transmission information sequence length and the LDPC code block length. However, there is a problem that, due to padding or puncturing, the coding rate changes or redundant sequence transmission is required.
In such an LDPC code of a block code (hereinafter referred to as “LDPC-BC” (Low-Density Parity-Check Block Code)), an LDPC convolutional code (hereinafter referred to as “LDPC-CC” (Low-Density Parity-Check Convolutional Code)), which can encode and decode an information sequence of an arbitrary length, is studied (see Non-Patent Document 1).
An LDPC-CC code is a convolutional code defined by a low-density parity check matrix. As an example, FIG. 1 shows a parity check matrix H[0, n]T of LDPC-CC codes of coding rate R=½ (=b/c). Here, “n” represents the transmission information sequence length, and “T” represents the transposed matrix.
As shown in the figure, elements h1(m)(t) and h2(m)(t) in parity check matrix H[0, n]T are “0” or “1” (m=0, 1, . . . , M). Also, all of the other elements than h1(m)(t) and h2(m)(t) included in parity check matrix H[0,n]T are “0's” (m=0, 1, . . . , M). As shown in FIG. 1, an LDPC-CC parity check matrix has a feature that “1's” are assigned only to the diagonal elements and to their nearby elements in the matrix, and “0's” are assigned to the lower left elements and upper right elements in the matrix.
Here, referring to an example of coding rate R=½ (=b/c), in the case of h1(0)(t)=1 and h2(0)(t)=1, an LDPC-CC coding is performed by the following equations 1 and 2 according to parity check matrix H[0, n]T.
                    [        1        ]                                                                      v                      1            ,            t                          =                  u          t                                    (                  Equation          ⁢                                          ⁢          1                )                                [        2        ]                                                                      v                      2            ,            t                          =                                            ∑                              i                =                0                            M                        ⁢                                                  ⁢                                                            h                  1                                      (                    i                    )                                                  ⁡                                  (                  n                  )                                            ⁢                              u                                  t                  -                  i                                                              +                                    ∑                              i                =                1                            M                        ⁢                                                  ⁢                                                            h                  2                                      (                    i                    )                                                  ⁡                                  (                  n                  )                                            ⁢                              v                                  2                  ,                                      t                    -                    i                                                                                                          (                  Equation          ⁢                                          ⁢          2                )            
Here, un represents the transmission information sequence, and v1,n and v2,n represent the transmission codeword sequences. Also, M is the memory length in the LDPC-CC code.
FIG. 2 shows an example of an LDPC-CC encoder that implements equations 1 and 2. As shown in FIG. 2, LDPC-CC encoder 10 is provided with shift registers 11-1 to 11-M and 14-1 to 14-M, weight multipliers 12-0 to 12-M and 13-0 to 13-M, weight control section 14 and mod 2 (i.e. exclusive OR calculation) adder 15.
Shift registers 11-1 to 11-M and shift registers 14-1 to 14-M hold v1,t-i and v2,t-i (i=0, . . . , M), respectively, transmit held values to the right neighboring shift registers at the timing the next input is received, and hold the values transmitted from the left neighboring shift registers.
Weight multipliers 12-0 to 12-M and 13-0 to 13-M switch the values of h1(m) and h2(m) between 0 and 1 (m=0, 1, . . . , M), based on control signals outputted from weight control section 14. Weight control section 14 transmits the values of h1(m) and h2(m) at a timing to weight multipliers 12-0 to 12-M and 13-0 to 13-M, based on a built-in parity check matrix. By performing mod 2 addition (i.e. exclusive OR calculation) of the output results of weight multipliers 12-0 to 12-M and 13-0 to 13-M, mod 2 adder 15 calculates v2,t-1.
By employing such a configuration, LDPC-CC encoder 10 can perform LDPC coding according to a parity check matrix.
Thus, an LDPC-CC encoder can be configured only with shift registers, adders and weight multipliers, and therefore has a feature that this encoder can be realized with a very simple circuit. Also, an LDPC-CC code is a kind of a convolutional code, so that it is not necessary to encode a transmission information sequence divided per fixed-length block, and it is possible to encode an information sequence of an arbitrary length.
Like LDPC-BC, it is possible to apply the sum-product algorithm to LDPC-CC decoding based on parity check matrix H. Therefore, a decoding algorithm based on maximum likelihood sequence estimation such as the Viterbi algorithm needs not be used, so that it is possible to complete decoding processing with low processing delay. Further, in Non-Patent Document 1, a decoding algorithm is proposed utilizing the shape of a parity check matrix in which “1's” are provided only near the diagonal elements in the matrix.
Non-Patent Document 1: Alberto Jimenez Felstorom, and Kamil Sh. Zigangirov, “Time-Varying Periodic Convolutional Codes With Low-Density Parity-Check-Matrix”, IEEE Transactions on Information Theory, Vol. 45, No. 6, pp. 2181-2191, September 1999.